package sort.onlogn;

/**
 * 快速排序：任取一个分区点将大于、小于该点的放到左右两边，然后重复下去
 * <p>
 * 非稳定、原地排序
 *
 * @author yeyangtao created at 16:08 2020/9/27
 */
public class QuickSort {
    public static void quickSort(int[] a) {
        int size = a.length;
        quick(a, 0, size - 1);
    }

    private static void quick(int[] a, int p, int r) {
        if (p >= r) return;
        //分区，返回分区点
        int q = partition(a, p, r);
        quick(a, p, q - 1);
        quick(a, q + 1, r);
    }

    /**
     * 将最后一个元素为分区点，并将小于它的放在左边，大于的在右边
     */
    private static int partition(int[] a, int p, int r) {
        int pivot = a[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (a[j] < pivot) {
                if (i == j) i++;
                else {
                    int temp = a[i];
                    a[i++] = a[j];
                    a[j] = temp;
                }
            }
        }
        int temp = a[i];
        a[i] = a[r];
        a[r] = temp;

        return i;
    }
}
